package LeetCodeTest.PrimaryAlgorithmTest.String;

import java.util.HashMap;

public class FirstUniqChar {
    /**
     * 字符串中的第一个唯一字符
     * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
     * 示例：
     * s = "leetcode"
     * 返回 0
     * s = "loveleetcode"
     * 返回 2
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn5z8r/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     *
     *
     */
    public static void main(String[] args) {
        String s = "loveleetcode";
        int i = firstUniqChar0(s);
        System.out.println(i);
    }

    /**
     * 方法三：将String s 转化为char数组。相较于思路同二，该方法时间复杂度更优
     * @param s 目标字符串
     * @return ans
     */
    public static int firstUniqChar1(String s) {
        int count[] = new int[26];
        char[] chars = s.toCharArray();
        //先统计每个字符出现的次数
        for (int i = 0; i < s.length(); i++)
            count[chars[i] - 'a']++;
        //然后在遍历字符串s中的字符，如果出现次数是1就直接返回
        for (int i = 0; i < s.length(); i++)
            if (count[chars[i] - 'a'] == 1)
                return i;
        return -1;
    }

    /**
     * 方法二：
     * 思路：两次循环。一次循环使用一个hashMap记录每个元素出现的次数，一次循环找出第一个出现一次的元素
     */
    public static int firstUniqChar0(String s) {
        int length = s.length();
        HashMap<Character,Integer> temp = new HashMap<>();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            temp.put(c,temp.getOrDefault(c,0)+1);
        }
        for (int i = 0; i < length; i++) {
            if (temp.get(s.charAt(i)) == 1){
                return i;
            }
        }
        return -1;
    }

    /**
     * 方法一：
     * 思路：使用String封装的方法 lastIndexOf(target) ,
     * 该方法可以找出 target 最后一次出现的索引。
     * 从前往后遍历。考虑到lastIndexOf，时间复杂度较高，不推荐
     * @param s 目标字符串
     * @return ans
     */
    public static int firstUniqChar(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i))){
                return i;
            }
        }
        return -1;
    }
}
